package 贪心;

public class leetcode1413 {
	/*
	 	在 lc 1446 的基础上， 进行的 一个 想法（但是 思想 是错误的！）
	 	TTFTT 这个字符串， 就会出现错误，用这种方式的话！
		利用 找到 字符串 中连续的 T 或者 F 的最长 长度，
		这种想法 是错的！
	 */
	public int solution(String str,int k){
		int ans =  1; // 防止 只有 一个 字符的情况!
		int count = 1;
		int len = str.length();
		for(int i = 0; i < len - 1;i++ ){
			if(str.charAt(i) == str.charAt(i + 1)){
				count++;
			}
			else{
				count = 1;
			}
			ans = Math.max(count,ans);
		}
		return ans + k >= len ? len : ans + k;
	}



	/*
	 lc 1446
	 */
	public int maxPower(String s) {
		int ans =  1, count = 1;
		for(int i = 0;i < s.length() - 1;i++){
			if(s.charAt(i) == s.charAt(i + 1)){
				count++;
			}
			else{
				count = 1;
			}
			ans = Math.max(ans,count);
		}
		return ans;
	}

	/*
	  滑动窗口
	 找出一个 i ~ j 内 T or F  字符数量   <= k 的最大长度的窗口
	  主要学习 其思想
	  其实 想明白之后，这个题，也不难
	 */
	public int right(String str,int k){
		return Math.max(getCnt(str,'T',k),getCnt(str,'F',k));
	}
	/*
	  滑动窗口函数,过程的一个 主体函数
	  标准的 滑动窗口!
	 */
	public int getCnt(String str,char ch,int k){
		int count = 0;
		int ans = 0;
		int j = 0;
		for(int i = 0; i < str.length();i++){
			if(str.charAt(i) == ch){
				count++;
			}
			while(count > k){
				if(str.charAt(j++) == ch){
					count--;
				}
			}
			ans = Math.max(ans,i - j + 1);
		}
		return ans;
	}

	/*
	 动态 规划
	 这种题 ,都能写出来  dp ,我也是 服了!
	 有点 类似于买卖股票的 最佳时机,那种动态规划的思想了!
	 f(i,k,status)
	 i: 索引
	 k : 操作次数
	 status : 0 表示 F , 1 表示 T
	 但是 这个 递归怎么写,有点 难度!
	 */
	class Solution {
		public int maxConsecutiveAnswers(String answerKey, int k) {
        /* dp[i][j][ch] 表示 [0, i] 范围内, 使用不超过j次操作后,
                        以 ch(01分别代表FT) 结尾的最大后缀长度
           dp[i] 只由 dp[i-1] 转移而来，可用滚动数组优化空间
         */
			int n = answerKey.length(), ans = 0;
			int[][] f = new int[k + 1][2];// dp[i-1]
			for (int i = 0; i < n; ++i) {
				int[][] g = new int[k + 1][2];// dp[i]
				if (answerKey.charAt(i) == 'T') {// 结尾为T
					for (int j = 0; j <= k; ++j) {
						// 使用1次操作把T变成F，与左边的F连接起来
						// 当前用了1次，左边就剩余j - 1次操作机会
						if (j > 0) g[j][0] = f[j - 1][0] + 1;
						// 不使用操作，直接与左边的T连接起来
						g[j][1] = f[j][1] + 1;
					}
				} else {// 结尾为F，与上面同理
					for (int j = 0; j <= k; ++j) {
						g[j][0] = f[j][0] + 1;
						if (j > 0) g[j][1] = f[j - 1][1] + 1;
					}
				}
				ans = Math.max(ans, g[k][0]);
				ans = Math.max(ans, g[k][1]);
				f = g;
			}
			return ans;
		}
	}

}
